// 20210628
// Go的编码经验还不足，今日参照了LeetCode CookBook的写法
// LeetCode CookBook项目地址：https://github.com/halfrost/LeetCode-Go.git 

package leetcode

func numBusesToDestination(routes [][]int, source, target int) int {
	if source == target {
		return 0
	}


	vertexMap := map[int][]int{}
	visited := make([]bool, len(routes))
	queue := []int{}
	res := 0


	for i := 0; i < len(routes); i++ {
		for _, v := range routes[i] {
			tmp := vertexMap[v]
			tmp = append(tmp, i)
			vertexMap[v] = tmp
		}
	}

	queue = append(queue, source)
	for len(queue) > 0 {
		res ++
		qlen := len(queue)
		for i := 0; i < qlen; i ++ {
			vertex := queue[0]
			queue = queue[1:]
			for _, bus := range vertexMap[vertex] {
				if visited[bus] == true {
					continue
				}

				visited[bus] = true
				for _, v := range routes[bus] {
					if v == target {
						return res
					}
					queue = append(queue, v)
				}
			}
		}
	}
	return -1
}
